Telecommunication usually includes transmitting sequences of electromagnetic symbols over a medium, such as but not limited to a wireless medium. During the transmission the sequence can be corrupted. Modern transmitters and receivers apply various measures to overcome said corruption and to provide robust communication links.
Transmitters usually receive an input information sequence and encode it by a forward-error correction device such as a convolutional encoder. The convolutional encoder generates an encoded information sequence that includes the input information signals as well as redundant signals. The encoded information sequence can be further processed in various manners and can also be modulated before being transmitted over the medium.
U.S. patent application 2004/0091067 of Ammer at al. titled “System and method for one-pass blind transport format detection”, which is incorporated herein by reference, provides a brief description of various processing stages applied by modern wideband code division multiple access (WCDMA) transmitters and modern WCDMA transmitters.
Receivers usually demodulate received signals and process them in order to reconstruct the input information signal sequence. The reception process usually includes Viterbi decoding.
Viterbi decoding is well known in the art. The following U.S. patents and patent applications, all being incorporated herein by reference, provide an example of prior art Viterbi decoders and Viterbi decoding methods: U.S. patent application 2003/0028844 of Coombs, titled “Method and apparatus for implementing a single cycle operation in a data processing system”; U.S. Pat. No. 6,575,864 of Hansquine, titled “method and apparatus for efficiently reading and storing state metrics in memory for high-speed ACS Viterbi decoder implementation”; U.S. patent application 2002/0126776 of Muck et al., titled “Viterbi decoder, method and unit therefore”; U.S. Pat. No. 5,987,638 of Yu et al., titled “Apparatus and method for computing the result of a Viterbi equation in a single cycle”.
Typically, the receiver has to know in advance the length of the received information sequences (also referred to as information frames, information blocks). Said knowledge can improve the performance of receivers and in some cases can even be critical.
Some telecommunication protocols, standard and methods use variable length information frames. For example, the third generation partnership project (3GPP™) defined a telecommunication protocol that uses variable sized frames (also referred to as communication channels).
More specifically, the standard defined multiple operational modes and three possible sizes of communication channels (class A, class B and class C) per mode. This protocol was defined in various papers including technical specification 3GPP TS 25.212 V6.0.0 which is incorporated herein by reference.
The transmitter can send to the receiver size information representative of the size of a transmitted information frame. On the other hand, the receiver can determine the size of a received information frame by its own. A well known method for determining the length of an information packet in knows as blind transport forward detection. This algorithm is described in Annex A of the 3GPP TS 25.212 V6.0.0, which is incorporated herein by reference.
In a nut shell, the blind transport forward detection (BFTD) algorithm (or sequence) includes applying forward trellis processing (also known as Viterbi decoding or feed forward process), a complex calculation of a variable denoted S(nend), and a comparison of this variable to a predefined threshold D. If S(nend) is equal to D or smaller than D then the algorithm proceeds by performing a Viterbi trace back process and applies a cyclic redundancy check (CRC) on the results of the trace back process.
The size of the information frame (or the location of the information frame end) can be determined by selecting one end point out of a known group of possible end points. If more than a single possible end point passes the CRC test and it's S(nend) is smaller than D then the algorithm selects the end point that is associated with the smallest S(nend). It is noted that the receiver can determine that the reception failed.
In mathematical terms S(nend)=−10 Log((a0(nend)−amin(nend))/(amax(nend)−amin(nend)), wherein a0(nend) is the path metric value at zero state of the trellis stage that corresponds to the nend′th possible end point, amin(nend) and amax(nend) are the minimum and maximum path metric values among all survivor paths of that trellis stage. In a typical trellis graph each trellis stage include 2T−1 states where T is the length of the convolutional encoder. In standard 3GPP TS 25.212 V6.0.0 T equals nine. Thus, the search for the minimal and maximal survivor paths is quite long.
U.S. patent application 2004/0091067 of Ammer et al. suggests to calculate a threshold T(nend) and to compare it to zero, instead of calculating S(nend) and comparing it to D. T(nend)=10D/10*((amax(nend)−amin(nend))−(a0(nend)−amin(nend)).
FIG. 1 illustrates an information frame 10, nine possible end points 11-19, and a portion of a trellis diagram 20 that corresponds to that information frame 10. The information frame 10 includes a payload, CRC bits and empty bits (a sequence of zero bits). The trellis diagram 20 includes multiple trellis stages, wherein nine trellis stages are associated with the nine possible end points. Each of these nine trellis stages is associated with an nend value that range between one to nine.
FIG. 2 illustrates a prior art method 30 for blind transport forward detection algorithm, as it appears in said Annex A of the 3GPP TS 25.212 V6.0.0.
Method 30 starts by stage 32 of setting nend to one (starting from the first possible end point), setting another variable nend′ to zero and setting Smin to D.
Stage 32 is followed by stage 34 of performing Viterbi decoding (also referred to as forward trellis process or trellis feed forward process) from a start point to the trellis stage that corresponds to the nend′th possible end point.
Stage 34 is followed by stage 36 of calculating S(nend).
Stage 36 is followed by query stage 38 of determining if S(nend) is greater than D. If D>=S(nend) then query stage 38 is followed by stage 40 of performing a trace back process from the nend′th possible end point, in order to provide an nend′th hypothetical trellis path. If D<S(nend) then stage 38 is followed by query stage 50.
Stage 40 is followed by stage 42 of calculating CRC parity bits for the nend′th hypothetical trellis path.
Stage 42 is followed by query stage 44 of checking if the CRC passed or failed and if the CRC failed query stage 44 is followed by query stage 50. If the CRC passed then query stage 44 is followed by stage 46 of comparing S(nend) to Smin.
If S(nend)<Smin then query stage 46 is followed by stage 48 of setting Smin to S(nend) and setting nend′ to nend. Else query stage 46 is followed by query stage 50. Stage 48 is followed by query stage 50.
Query stage 50 involves checking if stages 34-48 were applied to all possible end points (“is nend the maximal value?”).
If the answer is negative than query stage 50 is followed by stage 52 of increasing nend and jumping to stage 34.
If all the possible end points were checked query stage 50 is followed by stage 54 of providing the end point associated with nend′ as the selected frame end point. If the value of nend′ is zero the received frame is declared to be in error.
There is a need to provide an efficient method and apparatus for locating an end of an information frame.